public class Processing
{
	// Skeletonization of the pattern
	public static int[][] skeletonize(int[][] pattern, int method, boolean printResults)
	{
		int height = pattern.length;
		int width = pattern[0].length;
		
		int[][] current = pattern.clone();
		int[][] last = null;
		int[] look = new int[8];
		
		int counter = 0;
		int aOfP = 0;
		int bOfP = 0;
		
		boolean change;
		
		// Loop through the array
		do
		{
			if (printResults) System.out.println("Iteration " + (++counter));
			
			// Save the last result and reset the change "flag"
			last = current;
			current = new int[height][width];
			change = false;
			
			// For each point in the image
			for (int i = 1; i != last.length - 1; ++i)
			{
				for (int j = 1; j != last[i].length - 1; ++j)
				{
					// If the point is already empty, skip it
					if (last[i][j] == 0)
					{
						current[i][j] = 0;
						continue;
					}
					
					// Zhang-Suen method
					else if (method == 1)
					{
						aOfP = 0;
						bOfP = 0;
						
						if (printResults)
						{
							System.out.println("The square is");
							System.out.println(last[i - 1][j - 1] + " " + last[i - 1][j] + " " + last[i - 1][j + 1]);
							System.out.println(last[i][j - 1] + " P " + last[i][j + 1]);
							System.out.println(last[i + 1][j - 1] + " " + last[i + 1][j] + " " + last[i + 1][j + 1]);
						}
						
						// If even iteration, use c and d
						if (counter % 2 == 0)
						{
							// Condition c
							if (!(last[i - 1][j] == 0 || last[i][j + 1] == 0 || last[i + 1][j] == 0))
							{
								if (printResults) System.out.println("Condition c not met.");
								current[i][j] = 1;
								continue;
							}
							
							// Condition d
							if (!(last[i][j + 1] == 0 || last[i + 1][j] == 0 || last[i][j - 1] == 0))
							{
								if (printResults) System.out.println("Condition d not met.");
								current[i][j] = 1;
								continue;
							}
						}
						
						// If odd iteration, use c' and d'
						else
						{
							// Condition c'
							if (!(last[i - 1][j] == 0 || last[i][j + 1] == 0 || last[i][j - 1] == 0))
							{
								if (printResults) System.out.println("Condition c' not met.");
								current[i][j] = 1;
								continue;
							}
							
							// Condition d'
							if (!(last[i - 1][j] == 0 || last[i + 1][j] == 0 || last[i][j - 1] == 0))
							{
								if (printResults) System.out.println("Condition d' not met.");
								current[i][j] = 1;
								continue;
							}
						}
						
						//Fill the array with the surrounding pixels
						look[0] = last[i - 1][j];
						look[1] = last[i - 1][j + 1];
						look[2] = last[i][j + 1];
						look[3] = last[i + 1][j + 1];
						look[4] = last[i + 1][j];
						look[5] = last[i + 1][j - 1];
						look[6] = last[i][j - 1];
						look[7] = last[i - 1][j - 1];
						
						for (int k = 0; k != look.length; ++k)
						{
							// Condition a
							if (look[k] != 0) ++bOfP;
							
							// Condition b
							if (look[k] == 0 && look[(k + 1) % look.length] == 1) ++aOfP;
						}
						
						if (bOfP < 2 || bOfP > 6)
						{
							if (printResults) System.out.println("Condition a not met. B(p) is " + bOfP);
							current[i][j] = 1;
							continue;
						}
						
						if (aOfP != 1)
						{
							if (printResults) System.out.println("Condition a not met. A(p) is " + aOfP);
							current[i][j] = 1;
							continue;
						}
						
						if (printResults) System.out.println("B(p) is " + bOfP + ", A(p) is " + aOfP + ", P has been deleted.");
						current[i][j] = 0;
						change = true;
					}
				}
			}
			
		} while (change);
		// continue looping if we want continuous filling until
		// there is no change from one iteration to the next.
		
		return current;
	}
	
	// Calculate and correct the slant using moments
	public static int[][] slantCorrection(int[][] array)
	{
		int xPrime = 0;
		
		double u_11 = GeneralFunctions.findCentralMoment(array, 1, 1);
		double u_02 = GeneralFunctions.findCentralMoment(array, 0, 2);
		
		// Because my y's are flipped (0 is highest point), I use u_11 not -u_11
		double tanTheta = u_11 / u_02;

		double m_01 = GeneralFunctions.findGeometricMoment(array, 0, 1);
		double m_00 = GeneralFunctions.findGeometricMoment(array, 0, 0);
		
		double y_c = m_01/m_00;
		
		int[][] processedArray = new int[array.length][array[0].length];
		
		// For all points in the original array
		for (int i = 0; i != array.length; ++i)
		{
			for (int j = 0; j != array[i].length; ++j)
			{
				if (array[i][j] == 0)
				{
					continue;
				}
				
				// If the value of a point is 1, determine its x value
				// for the processed array
				xPrime = (int)(Math.floor(j - (i - y_c)*tanTheta));
				
				// If the point calculated falls within the image bounds,
				// place it in the new array
				if (xPrime >= 0 && xPrime < array[0].length)
				{
					processedArray[i][xPrime] = array[i][j];
				}
			}
		}
		
		return processedArray;
	}
	
	// Normalization with the choice of two methods: linear and moment
	public static int[][] normalization(int[][] array, int newWidth, int newHeight, int method)
	{
		int[][] processedArray = new int[newHeight][newWidth];
		int left=0, right=0, top=0, bottom=0;
		int oldWidth = array[0].length;
		int oldHeight = array.length;
		if (method == 3) {
			boolean foundL = false;
			for(int x=0; x!=oldWidth; x++) {
				for(int y=0; y!=oldHeight; y++) {
					if(array[y][x] != 0) {
						if (!foundL) {
							left = x;
							foundL = true;
							
						}
						right = x;
						break;
					}
				}
			}
			
			boolean foundT = false;
			for(int y=0; y!=oldHeight; y++) {
				for(int x=0; x!=oldWidth; x++) {
					if(array[y][x] != 0) {
						if (!foundT) {
							top = y;
							foundT = true;
						}
						bottom = y;
						break;
					}
				}
			}
			oldWidth = right - left;
			oldHeight = bottom - top;
		}
		
		
		double alpha = (double)newWidth / oldWidth;
		double beta = (double)newHeight / oldHeight;
		
		int x, y = 0;
		
		// Linear normalization
		if (method == 1 || method == 3)
		{
			for (int i = 0; i != newHeight; ++i)
			{
				for (int j = 0; j != newWidth; ++j)
				{
					// New x and y are calculated with backward mapping
					x = (int)(Math.floor(j / alpha)) + left;
					y = (int)(Math.floor(i / beta)) + top;
					
					// The value of the mapped pixel is placed in the new array
					processedArray[i][j] = array[y][x];
				}
			}
		}
		
		// Moment normalization
		if (method == 2)
		{
			double m_10 = GeneralFunctions.findGeometricMoment(array, 1, 0);
			double m_01 = GeneralFunctions.findGeometricMoment(array, 0, 1);
			double m_00 = GeneralFunctions.findGeometricMoment(array, 0, 0);
			
			double x_c = m_10/m_00;
			double y_c = m_01/m_00;
			double xPrime_c = newWidth / 2.0;
			double yPrime_c = newHeight / 2.0;
			
			for (int i = 0; i != newHeight; ++i)
			{
				for (int j = 0; j != newWidth; ++j)
				{
					// New x and y are calculated with backward moment mapping
					x = (int)(Math.round((j - xPrime_c) / alpha + x_c));
					y = (int)(Math.round((i - yPrime_c) / beta) + y_c);
					
					// The value of the mapped pixel is placed in the new array
					// if its x and y are valid. This way, I do not have to adjust
					// the bounds of the image
					if (y >= 0 && x >= 0 && y < array.length && x < array[0].length) processedArray[i][j] = array[y][x];
				}
			}
		}
		
		return processedArray;
	}
	
	// Contour extraction
	public static int[][] extractContour(int[][] array, boolean debug)
	{
		int initialX = 0, initialY = 0;
		int currentX = 0, currentY = 0;
		boolean found = false;
		boolean clockWise = false;
		String direction = "Left";
		boolean onePoint = false;
		
		// I use a two dimensional array to store the contour points so
		// that I can print the contour like any other processed image
		int[][] processedArray = new int[array.length][array[0].length];
		
		// Find the left most bottom pixel
		for (int i = 0; i != array[0].length; ++i)
		{
			for (int j = array.length - 1; j != -1; --j)
			{
				// When found, break
				if (array[j][i] == 1)
				{
					initialX = i;
					initialY = j;
					found = true;
					break;
				}
			}
			
			if (found) break;
		}
		
		if (debug) System.out.println("The starting point is " + initialX + ", " + initialY);
		
		// Put the initial point in processed array (B) and move left
		processedArray[initialY][initialX] = array[initialY][initialX];
		currentX = initialX - 1;
		currentY = initialY;
		
		if (debug) System.out.println("X and Y are now " + currentX + ", " + currentY);
		if (debug) System.out.println("Entering the while loop");
		
		// While not back at the first point with at least two contour points
		while (currentX != initialX || currentY != initialY || !onePoint)
		{
			// If the point is black and turning direction is not clockwise
			if (array[currentY][currentX] == 1 && !clockWise)
			{
				if (debug) System.out.println("Black point and counter clockwise.");
				if (debug) System.out.println("Added " + currentX + ", " + currentY + " to the new array.");
				if (!onePoint && debug) System.out.println("This is the first point added.");
				
				// Add point to B
				processedArray[currentY][currentX] = 1;
				onePoint = true;
			}
			// If the point is black and turning direction is clockwise
			else if (array[currentY][currentX] == 1 && clockWise)
			{
				if (debug) System.out.println("Black point and clockwise.");
				if (debug) System.out.println("Added " + currentX + ", " + currentY + " to the new array.");
				if (!onePoint && debug) System.out.println("This is the first point added.");
				if (debug) System.out.println("Rotation is now counter clockwise");
				
				// Add point to B and change direction
				processedArray[currentY][currentX] = 1;
				onePoint = true;
				clockWise = !clockWise;
			}
			// If the point is not black and turning direction is not clockwise
			else if (array[currentY][currentX] == 0 && !clockWise)
			{
				if (debug) System.out.println("White point and counter clockwise.");
				if (debug) System.out.println("Rotation is now clockwise");
				
				// Change direction
				clockWise = !clockWise;
			}
			// If the point is not black and turning direction is clockwise
			else if (array[currentY][currentX] == 0 && clockWise)
			{
				if (debug) System.out.println("White point and clockwise.");
				if (debug) System.out.println("Nothing to do");
				
				// Nothing to do
			}
			
			// Adjust direction
			if (clockWise)
			{
				if (direction == "Left") direction = "Up";
				else if (direction == "Up") direction = "Right";
				else if (direction == "Right") direction = "Down";
				else direction = "Left";
			}
			else
			{
				if (direction == "Left") direction = "Down";
				else if (direction == "Down") direction = "Right";
				else if (direction == "Right") direction = "Up";
				else direction = "Left";
			}
			
			if (debug) System.out.println("Moving " + direction);
		
			// Move according to the new direction
			if (direction == "Left") --currentX;
			else if (direction == "Down") ++currentY;
			else if (direction == "Right") ++currentX;
			else --currentY;
			
			if (debug) System.out.println("X and Y are now " + currentX + ", " + currentY);
		}
		
		if (debug) System.out.println("Exiting the while loop");
		
		return processedArray;
	}
	
	// Filling of the pattern
	public static int[][] fill(int[][] pattern, int method, boolean continuous, boolean printResults)
	{
		int height = pattern.length;
		int width = pattern[0].length;
		
		int[][] current = pattern.clone();
		int[][] last = null;
		
		int counter = 0;
		
		boolean change;
		
		// Loop through the array
		do
		{
			if (printResults) System.out.println("Iteration " + (++counter));
			
			// Save the last result and reset the change "flag"
			last = current;
			current = new int[height][width];
			change = false;
			
			// For each point in the image
			for (int i = 1; i != last.length - 1; ++i)
			{
				for (int j = 1; j != last[i].length - 1; ++j)
				{
					// If the point is already filled, skip it
					if (last[i][j] == 1)
					{
						current[i][j] = 1;
						continue;
					}
					
					// x1 = x0 + bf(h + d) + hd(b + f)
					else if (method == 1)
					{
						// If true, fill the point and note that a change has been made
						if ((last[i - 1][j] == 1 && last[i + 1][j] == 1 &&
								(last[i][j - 1] == 1 || last[i][j + 1] == 1)) ||
							(last[i][j - 1] == 1 && last[i][j + 1] == 1 &&
								(last[i - 1][j] == 1 || last[i + 1][j] == 1)))
						{
							current[i][j] = 1;
							
							if (printResults) System.out.println("Change at [" + i + "][" + j + "].");
							
							change = true;
						}
						else
						{
							current[i][j] = 0;
						}
					}
					
					// x1 = x0 + ae + bf + cg + hd
					else if (method == 2 || method == 0)
					{
						// If true, fill the point and note that a change has been made
						if ((last[i - 1][j - 1] == 1 && last[i + 1][j + 1] == 1) ||
							(last[i - 1][j] == 1 && last[i + 1][j] == 1) ||
							(last[i - 1][j + 1] == 1 && last[i + 1][j - 1] == 1) ||
							(last[i][j - 1] == 1 && last[i][j + 1] == 1))
						{
							current[i][j] = 1;
							
							if (printResults) System.out.println("Change at [" + i + "][" + j + "].");
							
							change = true;
						}
						else
						{
							current[i][j] = 0;
						}
					}
				}
			}
			
		} while (continuous && change);
		// continue looping if we want continuous filling until
		// there is no change from one iteration to the next.
		
		return current;
	}
	
	// Thinning
	public static int[][] thin(int[][] pattern, boolean continuous, boolean printResults)
	{
		int height = pattern.length;
		int width = pattern[0].length;
		
		int[][] current = pattern.clone();
		int[][] last = null;
		
		int counter = 0;
		
		boolean change;
		
		// Loop through the array
		do
		{
			if (printResults) System.out.println("Iteration " + (++counter));
			
			// Save the last result and reset the change "flag"
			last = current;
			current = new int[height][width];
			change = false;
			
			// For each point in the image
			for (int i = 1; i != last.length - 1; ++i)
			{
				for (int j = 1; j != last[i].length - 1; ++j)
				{
					// If the point is already empty skip it
					if (last[i][j] == 0)
					{
						current[i][j] = 0;
						continue;
					}
					
					// x1 = x0 [(a + b + h)(d + e + f) + (b + c + d)(f + g + h)]
					else
					{
						// If true, remove the point and note that a change has been made
						if (((last[i - 1][j] == 1 || last[i - 1][j + 1] == 1 || last[i][j + 1] == 1) &&
								(last[i + 1][j] == 1 || last[i + 1][j - 1] == 1 || last[i][j - 1] == 1)) ||
							((last[i][j - 1] == 1 || last[i - 1][j - 1] == 1 || last[i - 1][j] == 1) &&
								(last[i][j + 1] == 1 || last[i + 1][j + 1] == 1 || last[i + 1][j] == 1)))
						{
							current[i][j] = 1;
						}
						else
						{
							current[i][j] = 0;

							if (printResults) System.out.println("Change at [" + i + "][" + j + "].");
							
							change = true;
						}
					}
				}
			}
			
		} while (continuous && change);
		// continue looping if we want continuous thinning until
		// there is no change from one iteration to the next.
		
		return current;
	}
	
	 // Removes solo pixels
    public static int[][] removeSoloPoints(int[][] pattern)
    {
            // For each point in the image
            for (int i = 1; i != pattern.length - 1; ++i)
            {
                    for (int j = 1; j != pattern[i].length - 1; ++j)
                    {
                            // If the point is already empty skip it
                            if (pattern[i][j] == 0)
                            {
                                    continue;
                            }
                                    
                            else
                            {
                                    // If alone, remove the point
                                    if (pattern[i - 1][j] == 0 &&
                                            pattern[i][j + 1]  == 0 &&
                                            pattern[i + 1][j] == 0 &&
                                            pattern[i][j - 1] == 0 &&
                                            pattern[i - 1][j + 1] == 0 &&
                                            pattern[i + 1][j + 1] == 0 &&
                                            pattern[i + 1][j - 1] == 0 &&
                                            pattern[i - 1][j - 1] == 0)
                                    {
                                            pattern[i][j] = 0;
                                    }
                            }
                    }
            }
            
            return pattern;
    }
	
	public static int[][] gaussianBlur(int[][] pattern, double sigma)
    {
            double[][] window = new double[3][3];
            double power = 0;
            double sum = 0;
            
            int[][] blurredPattern = new int[pattern.length][pattern[0].length];
            
            // Calculate window values
            for (int i = 0; i != window.length; ++i)
            {
                    for (int j = 0; j != window[i].length; ++j)
                    {
                            power = - ( ( (1 - j)*(1 - j) + (1 - i)*(1 - i) )/(2*sigma*sigma) );
                            window[i][j] = (1.0 / (2*Math.PI*sigma*sigma))*Math.pow(Math.E, power);
                            sum += window[i][j];
                    }
            }
            
            // Adjust window values so that they sum to 1
            for (int i = 0; i != window.length; ++i)
            {
                    for (int j = 0; j != window[i].length; ++j)
                    {
                            window[i][j] *= (1.0 / sum);
                    }
            }
            
            // Find new pixel values
            for (int i = 1; i != pattern.length - 1; ++i)
            {
                    for (int j = 1; j != pattern[0].length - 1; ++j)
                    {
                            sum = 0;
                            
                            sum += pattern[i - 1][j - 1]*window[0][0];
                            sum += pattern[i - 1][j]*window[0][1];
                            sum += pattern[i - 1][j + 1]*window[0][2];
                            
                            sum += pattern[i][j - 1]*window[1][0];
                            sum += pattern[i][j]*window[1][1];
                            sum += pattern[i][j + 1]*window[1][2];
                            
                            sum += pattern[i + 1][j - 1]*window[2][0];
                            sum += pattern[i + 1][j]*window[2][1];
                            sum += pattern[i + 1][j + 1]*window[2][2];
                            
                            blurredPattern[i][j] = (int)Math.floor(sum);
                    }
            }
            
            return blurredPattern;
    }
}